//给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。 
//
// 注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2
//输出："110"
//解释：(-2)² + (-2)¹ = 2
// 
//
// 示例 2： 
//
// 
//输入：n = 3
//输出："111"
//解释：(-2)² + (-2)¹ + (-2)⁰ = 3
// 
//
// 示例 3： 
//
// 
//输入：n = 4
//输出："100"
//解释：(-2)² = 4
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 10⁹ 
// 
//
// Related Topics 数学 👍 218 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-04-28 23:22:22
 * @description 1017.负二进制转换
 */
public class ConvertToBase2{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ConvertToBase2 fun=new ConvertToBase2();
	 	 Solution solution = fun.new Solution();
		  solution.baseAny(6,-2);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*模拟进位
		 * 将 n 转换为二进制数，并将二进制数中的每一位转换为「负二进制」中的每一位，
		 * 变换后的数列为 bits；
           将 bits从低位向高位进行「进位」运算，即将 bits\中的每一位都变为 0 或者 1；
           去掉前导 0 以后，将 bits转换为字符串返回即可。
           * 进位a=(val-余数r)/进制x，其中r=val&1
*/
	public String baseNeg2(int n) {
		if (n == 0) {
			return "0";
		}
		int[] bits = new int[32];
		//转化为二进制，最高32位
		/*n=7时，二进制位111，从右往左遍历，碰到第二个1时，这
		在负二进制里表示-2，我们直接给n加上4修正，、
		二进制位变为1011，然后遍历到左边第一个1时，
		这里在负二进制里表示-8，我们再给n加上16修正，
		变为11011，即为n=7的负二进制表示*/
		for (int i = 0; i < 32 && n != 0; i++) {
			if ((n & 1) != 0) {
				bits[i]++;
				//如果i是奇数（即二进制下末位为1）,就是负数
				//则将下一个位置（i+1）的bits数组的元素加1。
				// 这个操作是在统计每两位连续为1的情况下，保证其正确统计。
				if ((i & 1) != 0) {
					bits[i + 1]++;
				}
			}
			n >>= 1;
		}
		int carry = 0;
		for (int i = 0; i < 32; i++) {
			int val = carry + bits[i];
			bits[i] = val & 1;
			//进位
			carry = (val - bits[i]) / (-2);
		}
		int pos = 31;
		StringBuilder res = new StringBuilder();
		//去掉前面的0
		while (pos >= 0 && bits[pos] == 0) {
			pos--;
		}
		//添加字符串
		while (pos >= 0) {
			res.append(bits[pos]);
			pos--;
		}
		return res.toString();
	}

		 /*进制转换：
		 * 每一个数n的x进制
		 * 都可以展开为
		 * a*x^3+b*x^2+c*x^1+d*x^0
		 * 对于2/-2进制，奇偶性可以得到d
		 * 对于其他进制，如果x大于0，则d=n%x
		 * 但若x为负数，则这里还是需要针对不同语言的除法特性去分析，
		 * 可能需要在 n % x 的基础上再进行一些运算操作得到 d
		 * 之后让n-=d,n/=x
		 * 实际上是抹去低位，然后右移*/
    public String baseNeg21(int n) {
			if(n==0) return "0";
			String res="";
			while (n!=0){
				if(n%2==0){
					res+="0";
				}else {
					n-=1;
					res+=1;
				}
				n/=-2;
			}
			return  new StringBuilder(res).reverse().toString();
    }

	/*
	* // 【负三进制】
// 对于负三进制表达式来说，每位的可能取值为0 1 2，
* 因此只有为0 1 2的余数是有效的，即我们要找的当前最低位f应是这些有效余数
// 但由于语言特性，n % -3 的可能结果是-2 -1 0 1 2，
* 其中的-2和-1不是我们需要的余数，因此需要进行转换，
* 给他们都加一个 base 使余数落在 [0,base-1] 的区间上
// 之后对于得到的这个有效余数去进行后续常规操作即可
// 说明为什么给 r 加个 base 不影响结果（或者说是正确的）：
//   n = a * base + r
//     = (a - 1) * base + (r + base)
//   1.  从前面系数中挪一个 base 给 r 并不影响该等式的成立
//   2.  我们要找的就是满足
* n = …… + a * (base)^5 + b * (base)^4 + c * (base)^3 + d * (base)^2 + e * (base)^1 + f * (base)^0
* 的各项有效系数（即过程中的余数）
//       在循环的每一步都需要确定一个有效系数，并在这个系数的基础上继续找后续的系数
*/
	public String baseNeg3(int n) {
		if (n == 0)
			return "0";

		String ans = "";
		while (n != 0)
		{
			// 获取当前最低位f
			// n % -3 的可能取值为 -2 -1 0 1 2
			int r = n % -3;
			if (r == 0) // 当前最低位本身就为0，后续直接抹去这个最低位，除以-3即可
				ans += "0";
			else if (r < 0) // -2 -1
			{
				r += 3; // 要将余数转换为有效的范围，正数的余数才是我们要找的那个余数，作为f
				n -= r; // 将最低位的值f抹去，保证后续 n /= -3 是整除，从而保证不同语言的通用性
				ans += '0' + r;
			}
			else // r > 0
			{
				n -= r;
				ans += '0' + r;
			}

			// 将n的进制表达式向右移一位
			n /= -3;
		}
		return new StringBuilder(ans).reverse().toString();
	}

	public String baseAny(int n, int base)
	{
		if (n == 0)
			return "0";

		StringBuilder ans= new StringBuilder();
		while (n != 0)
		{
			// 获取当前最低位
			int r = n % base;
			if (r < 0)     // 说明 base 必为负数
				r -= base; // 保证找到的余数在有效范围 [0, base - 1] 内
			n -= r;        // 将最后一位抹零，保证后续是整除，从而保证不同语言通用
			if (r >= 10)
				ans.append((char)('A' + r - 10));
			else
				ans.append((char)('0' + r));

			// 将n的进制表达式向右移一位
			n /= base;
		}
		return ans.reverse().toString();
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
